/*
 * SenseBarrier.java
 *
 * Created on August 3, 2005, 10:49 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 *
 * This work is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
 * http://i.creativecommons.org/l/by-sa/3.0/us/88x31.png
 */

package barrier.senseBarrier;

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import barrier.Barrier;
import barrier.ThreadID;

/**
 * 
 * @author Yoni Seroussi
 * @author Roei Raviv
 *
 * Sense-reversing barrier which splits the threads to 2 "sides" 
 * a "side" is a pool of CPUs that have memory locality with each other. 
 * 
 * Expected to run on the capricorn machine, expecting 64 threads to run on
 * one "side" and the other on second "side" - to minimize the expensive memory
 * updates between 2 sides.
 * using one globalSense boolean to communicate between both sizes.
 * only last thread should update this flag. 
 */
public class SplittedSenseBarrier implements Barrier {
    AtomicInteger countA; // how many threads have arrived
    AtomicInteger countB; // how many threads have arrived
    int size; // total number of threads
    private final int resetSize; // number of threads for each counter
    volatile boolean senseA; // object A sense
    volatile boolean senseB; // object B sense
    volatile boolean globalSense; // object's sense
    AtomicBoolean lastForGlobal; //while false we wait for the other to change global if false - I change the global coz other already got here. 
    ThreadLocal<Boolean> threadSense;
    private ThreadLocal<Integer> _threadId;

    /**
     * Constructor
     * 
     * @param n barrier width (assuming n is Even > 0)
     */
    public SplittedSenseBarrier(int n) {
        resetSize = (int) n/2; // each takes care of half of the threads
        countA = new AtomicInteger(resetSize); 
        countB = new AtomicInteger(resetSize);
        lastForGlobal = new AtomicBoolean(false);
        size = n;
        senseA = false;
        senseB = false;
        globalSense = false;
        threadSense = new ThreadLocal<Boolean>() {
            @Override
            protected Boolean initialValue() {
                return !globalSense;
            };
        };
        _threadId = new ThreadLocal<Integer>() {
            @Override
            protected Integer initialValue() {
                return ThreadID.get() % size;
            }
        };
    }

    /**
     * Wait for threads to catch up.
     */
    @Override
    public void await() {
        int me = _threadId.get();
        if (me < resetSize) {
            work(countA, senseA);
            return;
        }
        work(countB, senseB);
    }
    
    /**
     * @param countOfSide
     * @param sense
     */
    private void work(AtomicInteger countOfSide, boolean sense) {
        boolean mySense = threadSense.get();
        int position = countOfSide.getAndDecrement();
        if (position == 1) { // I'm last on side
            countOfSide.set(this.resetSize); // reset side counter
            if (lastForGlobal.getAndSet(true)) {
                // if was true means other set it before us, we're SOOO last... 
                lastForGlobal.set(false); // reset flag
                // release all sides
                globalSense = !globalSense;
            } else {
                // my side finished first wait for other.
                while (globalSense != mySense) {}
            }
            sense = mySense; // reverse sense
        } else {
            while (sense != mySense) {
            } // busy-wait
        }
        threadSense.set(!mySense);
    }
}
